class Solution1 {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null ){
            return -1;
        }
        if (haystack.length() < needle.length()){
            return -1;
        }
        char[] ch1 = haystack.toCharArray();
        char[] p = needle.toCharArray();
        int i = 0;
        int j = 0;
        int ps = i;
        int idex = -1;
        while (i < ch1.length && j < p.length){
            if (p[j] == ch1[i]){
               ps = i ;
                j++;
            }else{
                j = 0;
                i = ps;
            }
            if (j == p.length){
                return i;
            }
            i++;
        }
        return idex;
    }
}



class Solution2 {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null ){
            return -1;
        }
        if (haystack.length() < needle.length()){
            return -1;
        }
        int n = haystack.length();
        int m = needle.length();
        int i = 0;
        int j = 0;
        int ps = 0;
        while(i < n-m){
            ps = 0;
            j = i;
            while (ps < m ){
                if (haystack.charAt(j) == needle.charAt(ps)){
                    ps++;
                    j++;
                }else{
                    break;
                }

            }
            if (ps == m){
                return i;
            }else{
                i++;
            }
        }
        return -1;
    }
}


/**
 * 28. 实现 strStr()
 */
class Solution3 {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m > n){
            return -1;
        }
        int i = 0;
        int j = 0;
        int ps = 0;
        while(i < n){//也可以换成(i <=n-m) 防止越界 i剩下的长度小于m 不可能有子串了
            ps = 0;
            j = i;
            while (ps < m && j<n){//防止越界
                if (haystack.charAt(j) == needle.charAt(ps)){
                    ps++;
                    j++;
                }else{
                    break;
                }

            }
            if (ps == m){
                return i;
            }else{
                i++;
            }
        }
        return -1;
    }
}

/**
 * 35. 搜索插入位置
 */
class Solution4 {
    public int searchInsert(int[] nums, int target) {
        for(int i = 0;i<nums.length;i++){
            if (nums[i] >= target){
                return i;
            }
        }
        return nums.length;
    }
}

/**
 * 58. 最后一个单词的长度
 */
class Solution5 {
    public int lengthOfLastWord(String s) {
        String str = s.trim();
        int n = str.length()-1;
        int ct = 0;
        for (int i = n;i>=0;i--){
            if (str.charAt(i) != ' '){
                ct++;
            }else{
                break;
            }
        }
        return ct;
    }
}


/**
 * 66. 加一
 */

class Solution6 {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length-1;i>=0;i--){
            digits[i]++;
            digits[i] = digits[i]%10;//10%10 = 0;代表进位
            if (digits[i] != 0){
                return digits;
            }
        }
        //99 .. 这些情况需要手动进位
        digits = new int[digits.length+1];
        digits[0] = 1;
        return digits;
    }
}

/**
 * 67. 二进制求和
 */
class Solution7 {
    public String addBinary(String a, String b) {
        if (null == a || a.length() == 0) return b;
        if (null == b || b.length() == 0) return a;

        StringBuilder str = new StringBuilder();
        int i = a.length()-1;
        int j = b.length()-1;
        int ct = 0;//用来进位
        while (i>=0 || j>= 0 || ct != 0){//如果没有遍历完两个数，或者还有进位
            if(i >= 0) {
                ct += a.charAt(i--) - '0'; //‘1’ - ‘0’ = 1
            }
            if (j >= 0){
                ct += b.charAt(j--) - '0';
            }
            str.append(ct%2);//ct%2  进位
            ct /= 2;//进位
        }

        return  str.reverse().toString();
    }
}